public class Test {

//    反转一个单链表
//
//            链表的中间结点
//
//    返回倒数第k个结点
//
//            合并两个链表
    class Solution {
        public ListNode reverseList(ListNode head) {
            if(head==null){
                return head;
            }
            //正常情况
            ListNode cur=head.next;
            head.next=null;
            while(cur!=null){
                ListNode curN=cur.next;
                cur.next=head;
                head=cur;
                cur=curN;
            }
            return head;
        }
    }

    class Solution {
        public ListNode middleNode(ListNode head) {

            ListNode slow=head;
            ListNode fast=head;
            while(fast!=null&&fast.next!=null){
                slow=slow.next;
                fast=fast.next.next;
            }
            return slow;
        }
    }

    class Solution {
        public int kthToLast(ListNode head, int k) {
            ListNode fast=head;
            ListNode slow =head;
            int count=0;
            while(count<k){
                fast=fast.next;
                count++;
            }
            while(fast!=null){
                fast=fast.next;
                slow=slow.next;
            }
            return slow.val;
        }
    }

    class Solution {
        public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
            ListNode headH=new ListNode();
            ListNode cur=headH;

            while(list1!=null&&list2!=null){
                if(list1.val<list2.val){
                    cur.next=list1;
                    list1=list1.next;
                    cur=cur.next;
                }
                else{
                    cur.next=list2;
                    list2=list2.next;
                    cur=cur.next;
                }

            }
            if(list1==null){
                cur.next=list2;
            }
            if(list2==null){
                cur.next=list1;
            }
            return headH.next;
        }
    }
//    判断环的入口点b
    public class Solution{
        public ListNode detectCycle(ListNode head){
            ListNode fast=head;
            ListNode slow=head;
            while(fast!=null&&fast.next!=null){
                fast=fast.next.next;
                slow=slow.next.next;
                if(fast==slow){
                    break;
                }
            }
            if(fast==null||fast.next==null){
                return null;
            }
            fast=head;
            while(fast!=slow){
                fast=fast.next;
                slow=slow.next;

            }
            return fast;
        }
}
}
